原文題目

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

題目摘要

1. 你是一位專業的劫匪，計劃在街上劫盜房子，每棟房子內有一定數量的金錢。由於鄰近的房子都有連接的警報系統，如果兩棟相鄰的房子被劫盜，警報會啟動並報警。目標在於不觸發警報的情況下，搶劫房子並獲得最大金額。
2. 輸入：一個整數陣列 nums，表示每棟房子中的金額。
3. 輸出：返回能夠搶劫的最大金額。
4. 限制：你不能同時劫盜兩棟相鄰的房子。

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

解題思路

1. 目標定義：
   • 使用 dp[i] 表示搶劫前 i+1 棟房子時能夠獲得的最大金額。
2. 情況列舉：
   • 如果不搶劫第 i 棟房子，那麼最大金額等於前 i 棟房子的最大金額，即 dp[i-1]。
   • 如果搶劫第 i 棟房子，那麼不能搶劫第 i-1 棟房子，則最大金額為第 i 棟房子的金額加上前 i-2 棟房子的最大金額，即 nums[i] + dp[i-2]。
   • 因此，dp[i] = max(dp[i-1], dp[i-2] + nums[i])。
3. 初始定義：
   • dp[0] 等於第一棟房子的金額，即 nums[0]。
   • dp[1] 等於第一棟和第二棟房子金額中的較大值，即 max(nums[0], nums[1])。
4. 計算結果：
   • 透過遍歷所有房子，利用上述狀態轉移方程更新 dp 陣列，最終 dp[n-1] 會包含可以搶劫的最大金額，其中 n 是房子的總數。

程式碼

class Solution {
    public int rob(int[] nums) {
        //當輸入的房屋數量為空或不存在時，直接返回0
        if(nums==null || nums.length==0){ 
            return 0;
        }
        //當只有一棟房子時，直接返回該房子的金額
        if(nums.length==1){ 
            return nums[0];
        }
        //建立一個動態規劃(DP)陣列，用來存儲每個房子到目前為止的最大金額
        int[] dp = new int[nums.length];
        //第一棟房子的最大金額就是該房子的金額
        dp[0] = nums[0];
        //第二棟房子的最大金額是搶劫第一棟和第二棟之間的較大者
        dp[1] = Math.max(nums[0], nums[1]);
        //從第三棟房子開始，計算每個房子所能搶到的最大金額
        for(int i = 2; i < nums.length; i++){
            //比較：不搶這棟房子（即前一棟房子的最大金額 dp[i-1]）
            //或者搶這棟房子加上前兩棟的最大金額（即 dp[i-2] + nums[i]）
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i]);
        }
        //回傳最後一棟房子（即整個房屋陣列）的最大搶劫金額
        return dp[nums.length-1];
    }
}

結論： 在這題「 House Robber 」讓我們看到動態規劃的實際應用，就像在生活中面對選擇時，我們常常需要權衡利弊。這題目要求我們在搶劫房子時不能犯錯，每一步都必須考慮最優解。通過記錄每一步的最優結果，我們能夠找到最佳的搶劫策略，最大化收益。這種解題方式告訴我們，即使在有約束條件的情況下，合理規劃和系統化的思考能讓我們達到最佳效果。